package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/5 14:34
 */
public class J47 {

    // https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
    // 暴力尝试
    public static int maxValue(int[][] grid) {
        return process(grid, 0, 0);
    }

    public static int process(int[][] grid, int r, int c) {
        if(r == grid.length || c == grid[0].length) {
            return -1;
        }
        if(r == grid.length-1 && c == grid[0].length-1) {
            return grid[r][c];
        }
        int p1 = process(grid, r+1, c) + grid[r][c];
        int p2 = process(grid, r, c+1) + grid[r][c];
        return Math.max(p1, p2);
    }

    public static int dp(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        int[][] dp = new int[R][C];
        dp[R-1][C-1] = grid[R-1][C-1];
        // 最后一行
        for (int c = C-2; c >=0; c--) {
            dp[R-1][c] = grid[R-1][c] + dp[R-1][c+1];
        }
        // 最后一列
        for (int r = R-2; r >=0; r--) {
            dp[r][C-1] = grid[r][C-1] + dp[r+1][C-1];
        }
        // 从下往上,从右往左推
        for (int r = R-2; r >= 0; r--) {
            for (int c = C-2; c >= 0; c--) {
                dp[r][c] = grid[r][c] + Math.max(dp[r+1][c], dp[r][c+1]);
            }
        }

        /*for (int[] arr : dp) {
            System.out.println(Arrays.toString(arr));
        }*/
        return dp[0][0];
    }

    // for test
    public static void main(String[] args) {
        int[][] grid = {
                {1, 2, 5},
                {3, 2, 1}
        };/*
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };*/
        System.out.println(maxValue(grid));
        System.out.println(dp(grid));

    }

}
